package com.smday.linkedlist;

import java.util.Stack;

/**
 * @author Summerday
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        //测试
        SingleLinkedList sll = new SingleLinkedList();
        HeroNode hero1 = new HeroNode(1, "松江1", "及时雨1");
        HeroNode hero2 = new HeroNode(34, "松江2", "及时雨2");
        HeroNode hero3 = new HeroNode(2, "松江3", "及时雨3");
        HeroNode hero4 = new HeroNode(77, "松江4", "及时雨4");
        //HeroNode hero5 = new HeroNode(4,"松江5", "及时雨5");

        //加入
        sll.addByOrder(hero1);
        sll.addByOrder(hero4);
        sll.addByOrder(hero2);
        sll.addByOrder(hero3);


        HeroNode d1 = sll.getDummyNode();

        System.out.println(d1);

        SingleLinkedList sll2 = new SingleLinkedList();
        HeroNode hero11 = new HeroNode(111, "松江1", "及时雨1");
        HeroNode hero22 = new HeroNode(341, "松江2", "及时雨2");
        HeroNode hero33 = new HeroNode(22, "松江3", "及时雨3");
        HeroNode hero44 = new HeroNode(727, "松江4", "及时雨4");

        //加入
        sll2.addByOrder(hero11);
        sll2.addByOrder(hero22);
        sll2.addByOrder(hero33);
        sll2.addByOrder(hero44);


        HeroNode d2 = sll2.getDummyNode();
        System.out.println(d2);

        HeroNode heroNode = sll.sortTwoLinkedList(d1, d2);
        sll.show(heroNode);
    }
}

class SingleLinkedList{

    //初始化头节点,头节点不动
    private HeroNode dummyNode = new HeroNode(0,"","");

    //添加节点到单项链表
    //1,找到当前链表的最后节点
    //2,即将最后这个节点的next指向新节点


    public HeroNode getDummyNode() {
        return dummyNode;
    }

    public void add(HeroNode node){
        //dummyNode节点不动,创建辅助指针
        HeroNode temp = dummyNode;
        //遍历链表找到最后
        while(temp.next!=null){
            temp = temp.next;
        }
        temp.next = node;
    }

    //按照no进行排序插入
    public void addByOrder(HeroNode newNode){

        //dummyNode不动
        HeroNode temp = dummyNode;
        //temp需要位于添加位置的前一个节点

        //标识添加的编号是否存在,默认为false
        boolean flag = false;

        while (true){
            //temp已经再最后
            if(temp.next == null){
                break;
            }
            //找到temp
            if(temp.next.no>newNode.no){
                 break;
            }else if(temp.next.no == newNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if(flag){
            //不能添加,编号已存在
            System.out.println("编号已存在!");
        }else {
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    public void update(HeroNode newNode){

        //判断是否为空
        if(dummyNode.next == null){
            System.out.println("链表为空");
            return;
        }

        //找到需要修改的节点,根据no编号
        HeroNode temp = dummyNode;
        //表示是否找到该节点
        boolean flag = false;

        while (true){
            if(temp.next == null){
                break;
            }
            if(temp.next.no == newNode.no){
                flag = true;
                break;
            }
            temp = temp.next;

        }
        if(flag){
            //temp.next.name = newNode.name;
            //temp.next.nickName = newNode.nickName;

            newNode.next = temp.next.next;
            temp.next = newNode;
        }else {
            System.out.println("未找到该节点");
        }
    }

    public void delete(int i){

        boolean flag = false;
        if(dummyNode.next == null){
            System.out.println("为空");
            return;
        }
        HeroNode temp = dummyNode;
        while(true){

            if(temp.next == null){
                break;
            }
            if(temp.next.no == i){
                flag = true;
                break;
            }
            temp = temp.next;

        }
        if(flag){
            temp.next = temp.next.next;
        }else {
            System.out.println("未找到该编号!");
        }


    }

    //显示链表
    public void show(HeroNode dummy){
        //判断链表是否为空
        if(dummy.next == null){
            System.out.println("链表为空!");
            return;
        }
        //头节点不能动,创建辅助指针
        HeroNode temp = dummy.next;
        //循环遍历
        while(temp!=null){
            //打印信息
            System.out.println(temp);
            //后移临时指针
            temp = temp.next;
        }
    }

    //单链表的反转(创建新链表,头插法)
    public void reverse(){
        HeroNode temp = dummyNode.next;
        //没有节点或只有一个节点,无需反转
        if(temp == null||temp.next == null){
            return;
        }
        HeroNode next = null;

        HeroNode reverseHead = new HeroNode(0,"","");

        while(temp!=null){

            //暂时保存当前节点的下一节点
            next = temp.next;
            //将当前节点的下一节点指向新链表的最前端
            temp.next = reverseHead.next;
            //将temp链接到新链表上
            reverseHead.next = temp;
            //temp向后移
            temp = next;

        }
        //将原头指向新链表
        dummyNode.next = reverseHead.next;
    }

    //单链表的反向遍历(栈的使用)
    public void reversePrint(){
        HeroNode cur = dummyNode.next;

        Stack<HeroNode> stack = new Stack<>();
        while(cur!=null){

            stack.push(cur);
            cur = cur.next;
        }

        while(stack.size()>0){

            System.out.println(stack.pop());

        }

    }
    //合并两个有序链表
    public HeroNode sortTwoLinkedList(HeroNode dummyNode1,HeroNode dummyNode2){
        HeroNode finalNode = new HeroNode(0,"","");
        HeroNode k1 = dummyNode1.next;
        HeroNode k2 = dummyNode2.next;
        HeroNode k3 = finalNode;
        while(k1!=null&&k2!=null){
            if(k1.no<k2.no){
                k3.next = k1;
                k1 = k1.next;
            }else {
                k3.next = k2;
                k2 = k2.next;
            }
            k3 = k3.next;
        }
        while(k1!=null){
            k3.next = k1;
            k1 = k1.next;
            k3 = k3.next;
        }
        while(k2!=null){
            k3.next = k2;
            k2 = k2.next;
            k3 = k3.next;
        }
        return finalNode;
    }

}

//定义一个HeroNode,每个HeroNode就是一个节点
class HeroNode{

    public int no;
    public String name;
    public String nickName;
    //next域
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                ", next=" + next +
                '}';
    }
}
